package 算法.leetcode.labuladong.structure;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Random;

/**
 * @author lchenglong
 * @date 2022/6/23
 */
public class O1时间插入删除和获取随机元素 {

    static class RandomizedSet {
        // ["RandomizedSet","remove","remove","insert","getRandom","remove","insert"]
        //[[],[0],[0],[0],[],[0],[0]]

        public static void main(String[] args) {
//            for (int i=0;i<10;i++){
//                System.out.println(new Random().nextInt(2));
//            }
            RandomizedSet randomizedSet = new RandomizedSet();
            boolean flag = randomizedSet.remove(0);
            flag = randomizedSet.remove(0);
            flag = randomizedSet.insert(0);
            int random = randomizedSet.getRandom();
            flag = randomizedSet.remove(0);
            flag = randomizedSet.insert(0);
//            System.out.println(random);
            System.out.println("<<<<<<<<<<<<<<<<<<<<");
        }


        HashMap<Integer, Integer> valToIndex ;
        List<Integer> nums;

        public RandomizedSet() {
            valToIndex = new HashMap<>();
            nums = new ArrayList<>();
        }

        public boolean insert(int val) {
            // 如果存在,则忽略
            if (valToIndex.containsKey(val)){
                return false;
            }
            nums.add(val);
            valToIndex.put(val,nums.size()-1);
            return true;
        }

        public boolean remove(int val) {
            if (!valToIndex.containsKey(val))return false;
            // 获取原来的索引
            int originIndex = valToIndex.get(val);
            int lastVal = nums.get(nums.size()-1);
            nums.set(originIndex,lastVal);
            nums.remove(nums.size()-1);
            valToIndex.put(lastVal,originIndex);
            valToIndex.remove(val);
            return true;
        }

        public int getRandom() {
            return (int) nums.get(new Random().nextInt(nums.size()));
        }
    }
}
